UVa/11515 - Cranes/a.cpp

   1 /*
   2   Problem: A - Cranes
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6  */
   7
   8 using namespace std;
   9 #include <algorithm>
  10 #include <iostream>
  11 #include <iterator>
  12 #include <sstream>
  13 #include <fstream>
  14 #include <cassert>
  15 #include <climits>
  16 #include <cstdlib>
  17 #include <cstring>
  18 #include <string>
  19 #include <cstdio>
  20 #include <vector>
  21 #include <cmath>
  22 #include <queue>
  23 #include <deque>
  24 #include <stack>
  25 #include <map>
  26 #include <set>
  27
  28 #define D(x) cout << #x " is " << x << endl
  29
  30 double pi = acos(-1.0);
  31
  32 struct crane{
  33   int x, y, r;
  34 };
  35
  36 inline double distsqr(int x1, int y1,    int x2, int y2){ return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}
  37
  38 bool colapse(crane &a, crane &b){
  39   return (distsqr(a.x,a.y,  b.x,b.y)  <= (a.r + b.r)*(a.r + b.r) );
  40 }
  41
  42 int main(){
  43   int C;
  44   for(cin >> C; C--;){
  45     int n;
  46     cin >> n;
  47
  48     vector<crane> v(n);
  49     for (int i=0; i<n; ++i) cin >> v[i].x >> v[i].y >> v[i].r;
  50
  51     vector<pair<int, int> > bad;
  52     for (int i=0; i<n; ++i)
  53       for (int j=i+1; j<n; ++j)
  54         if (colapse(v[i], v[j])){
  55             bad.push_back(make_pair(i, j));
  56             //cout << "choque " << i << " " << j << endl;
  57         }
  58
  59     int ans = 0;
  60
  61     for (int mask=1; mask < (1<<n); ++mask){
  62       bool ok = true;
  63       for (int i=0; i<bad.size(); ++i){
  64         int &x = bad[i].first, &y = bad[i].second;
  65         if ( (mask & (1 << x)) && (mask & (1 << y)) ){
  66             ok = false;
  67             break;
  68         }
  69       }
  70
  71         if (!ok) continue;
  72
  73         int sum = 0;
  74         for (int i=0; i<n; ++i){
  75           if (mask & (1 << i)){
  76             sum += v[i].r*v[i].r;
  77           }
  78         }
  79         ans = max(ans, sum);
  80     }
  81     cout << ans << endl;
  82
  83
  84   }
  85   return 0;
  86 }